package backtrack;

public class Solution_79 {

    int[] dx = {-1, 1, 0, 0};
    int[] dy = {0, 0, -1, 1};
    boolean[][] vis;

    public boolean exist(char[][] board, String word) {
        StringBuilder sb = new StringBuilder();
        int m = board.length;
        int n = board[0].length;
        vis = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dfs(board, word, i, j, sb);
            }
        }
        if (String.valueOf(sb).equals(word))
            return true;
        return false;
    }

    private void dfs(char[][] board, String word, int x, int y, StringBuilder sb) {
        if (x < 0 || y < 0 || x >= board.length || y >= board[0].length || String.valueOf(sb).equals(word) || vis[x][y]) {
            return;
        }
        sb.append(board[x][y]);
        vis[x][y] = true;
        for (int d = 0; d < 4; d++) {
            dfs(board, word, x + dx[d], y + dy[d], sb);
        }
        sb.deleteCharAt(sb.length() - 1);
        vis[x][y] = false;

    }
}
